package cn.edu.jxau.test;

import java.io.IOException;
import java.util.Arrays;

import cn.edu.jxau.util.LinkedQueue;

public class Main {

    public static void main(String[] args) throws IOException {

        int[] arr = { 9, 1, 0, 5, 4 };
        System.out.println(inversePairs(arr));
    }

    private static int inversePairs(int[] arr) {

        int[] temp = new int[arr.length];
        System.arraycopy(arr, 0, temp, 0, arr.length);
        int[] aux = new int[arr.length];
        return inversePairs(temp, aux, 0, temp.length - 1);
    }

    private static int inversePairs(int[] arr, int[] aux, int low, int high) {

        int mid = low + (high - low) / 2;
        int count = 0;
        if (high <= low) {
            return count;
        }
        count += inversePairs(arr, aux, low, mid);
        count += inversePairs(arr, aux, mid + 1, high);
        count += merge(arr, aux, low, mid, high);
        System.out.println(Arrays.toString(arr));
        return count;
    }

    private static int merge(int[] arr, int[] aux, int low, int mid, int high) {

        int count = 0;
        int i = low;
        int j = mid + 1;
        for (int k = low; k <= high; k++) {
            aux[k] = arr[k];
        }
        for (int k = low; k <= high; k++) {
            if (i > mid) { // 左半边耗尽
                arr[k] = aux[j++];
            } else if (j > high) {
                arr[k] = aux[i++];
            } else if (aux[i] < aux[j]) {
                arr[k] = aux[i++];
            } else {
                count += mid - i + 1;
                arr[k] = aux[j++];

            }
        }
        return count;
    }
}
